perm filename GEOMED[0,BGB]2 blob
sn#099384 filedate 1974-04-26 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 3.0 GEOMED AS A 3-D GEOMETRIC MODELING COMMAND LANGUAGE.
C00005 00003 3.1 Euler Routines.
C00009 00004 TABLE OF EULER ROUTINES
C00013 00005 3.2 Euclidean Routines.
C00015 00006 TABLE OF EUCLIDEAN ROUTINES.
C00017 00007 3.3 Image Synthesis Routines. {perspective projection}
C00018 ENDMK
C⊗;
3.0 GEOMED AS A 3-D GEOMETRIC MODELING COMMAND LANGUAGE.
3.0 Introduction.
3.1 Euler Routines.
3.2 Euclidean Routines.
3.3 Image Synthesis Routines.
3.0 Introduction.
GEOMED (Geometric Editor) is a system of subroutines for
manipulating winged edge polyhedra. The system has two distinctly
different manifestations: first, it appears as an interactive 3-D
drawing program and second, it appears as a geometric modeling
command language. It is the latter manifestation along with some of
the details of implementation that is the subject of this chapter.
GEOMED as an interactive drawing program is documented in reference
(**). As a language, GEOMED is all semantics with no syntax of its
own. As in the previous chapter, the language notation will continue
to be like ALGOL. There are about one hundred GEOMED subroutines
which take from zero to four arguments, return one or no values and
usually have considerable side effects on the data structures. The
subroutines can be grouped into four major functional classes:
utility routines, Euler routines, Euclidean Routines and image
synthesis routines. The utility routines (which will not be further
detailed) include input/output, trigonmetric functions, memory
management, a command scanner and device dependent display formating
routines. In general, the Euler routines perform topological
operations on links, the Euclidean routines perform geometric
computations on data and the image synthesis routines perform
photographic simulations on the model as a whole.
3.1 Euler Routines.
The Euler routines of GEOMED are based on the idea that an
arbitrary polyhedron can be created in steps that always maintain the
Euler relation: F-E+V=2*(B-H). Topologically, a simply connected
Eulerian polyhedral graph can be built up with only four creation
primitives which I have called: MKBFV, MKEV, MKFE and GLUEE. (The
ubiquitous prefixes "MK" and "KL", stand for "make" and "kill"
respectively). The MKBFV primitives takes no arguments and creates a
degenerate point polyhedron of one vertex, one face and one body
which is the minimal non-zero binding satisfying the equation. The
MKEV creates a new edge and a new vertex attached to the given vertex
in the given face. The MKFE creates a new face and a new edge, the
new edge is placed between the two given vertices. Finally the GLUEE
creates a handle or kills a body node by placing a new edge between
two given vertices and by removing the second of the two given faces.
Complementing the maker primitives there are four kill primitives
called KLBFEV, KLEV, KLFE and UNGLUEE. Completing the set, the ESPLIT
routine (mentioned in section **) is classified as an alternate form
of MKEV.
In theory, the advantages
of pure Euler primitives are that they assure valid
topology, full generality, reasonable simplicity and they achieve
a semantic level slightly higher than that of
manipulating the polyhedral nodes and links directly.
However, two major ommissions in the idea
orientation restrictions and face/vertex valence restrictions.
Further limitation of
geometric restrictions on a solid polyhedron:
face coplanarity, face convexity, surface self intersection,
still not a high enough good enough to be solid polyhedron
In practice, the primitives were coded once and have
changed little through several implementations of GEOMED.
{wires, lamina, sheets and wasp-wire}
TABLE OF EULER ROUTINES
---------------------------------------------------------------------
B. EULER MAKE PRIMITIVES:
1. BNEW ← MKBFV; Makes point polyhedron: 1 face, 1 vertex.
2. VNEW ← MKEV(F,V); Makes new edge and vertex such that:
VNEW = NVT(ENEW); V = PVT(ENEW);
VNEW ← ESPLIT(E); Makes new edge and vertex...
3. ENEW ← MKFE(V1,F,V2); Makes new face and edge such that:
FNEW = NFACE(ENEW); F = PFACE(ENEW);
V1 = PVT(ENEW); V2 = NVT(ENEW).
4. ENEW ← GLUEE(F1,V1,F2,V2); Makes new edge, Kills F2,
and makes a hole or kills a body.
V1 = PVT(ENEW); V2 = NVT(ENEW).
C. EULER KILL PRIMITIVES:
1. QNEW ← KLBFEV(Q); Kills B.F.E.V. entity. {FKILL},{EKILL}
2. F ← KLFE(E); Kills E and NFACE(E). Returns PFACE(E).
3. E ← KLEV(V); Kills V and PED(V). Returns other E of V.
V ← KLEV(E); Kills E and NVT(E). Returns PVT(E).
4. FNEW ← UNGLUE(E); Kills E; makes F; Returns the new face,
and kills a hole or makes a body.
D. FURTHER EULER ROUTINES:
1. BODY ← GLUE(FACE1,FACE2); Removes face1 and face2.
2. QNEW ← MKCOPY(ENTITY); Copy an entity.
3. FACE ← SWEEP(FACE,FLAG); Make prism on face (or sweep wire).
4. FACE ← ROTCOM(FACE); Rotation sweep wire face completion.
5. PEAK ← PYRAMID(FV); Make pyramid on a face (or vertex).
6. BODY ← FVDUAL(BODY); Apply face/vertex duality to a body.
7. BNEW ← MKCUBE(DX,DY,DZ); Create right rectangular prism.
8. BNEW ← MKCYLN(RADIUS,N,DZ); Create cylinder approximation.
9. BNEW ← MKBALL(RADIUS,M,N); Create sphere approximation.
---------------------------------------------------------------------
3.2 Euclidean Routines.
The Euclidean routines of GEOMED fall into three groups:
transformations, metrics and frame creations. The Euclidean
transformation primitives are translation, rotation, dilation and
reflection (following Klein's Erlangen Program, 1872). The Euclidean
metric routines compute distances, angles, areas, volumes and inertia
tensors; while the frame routines create or alter frame nodes.
Fundamental to these routines is the curious fact that a frame
node has two interpretations: it may be used to specify
a coordinate systems or it may be used to
represent a Euclidean transformation.
The Euclidean routines involving frames
can be explained in terms of the 4-D homogeneous coordinates
usual to computer graphics then both frame of reference and
transformations can be viewed as a tensor.
A tensor is a geometric object linear vector function.
TABLE OF EUCLIDEAN ROUTINES.
---------------------------------------------------------------------
EUCLIDEAN TRANSFORMATIONS
TRANS ← TRANSL(XWD(FRAME,BODY),DX,DY,DZ);
TRANS ← ROTATE(XWD(FRAME,BODY),WX,WY,WZ);
TRANS ← SHRINK(XWD(FRAME,BODY),KX,KY,KZ);
TRANS ← APTRAN(ENTITY,TRANS);
TRANS ← INTRAN(TRAN);
FRAME MAKERS
TRANS ← MKROT1(PAN,TILT,SWING); MAKE FROM EULER ANGLES.
TRANS ← MKFFRM(FACE); MAKE FACE FRAME.
TRANS ← MKQFRM(WX,WY,WZ); MAKE FROM ROTATION VECTOR.
FRAME ORTHONORMALIZATION.
NORM(FRAME) ;NORMALIZATION TO UNIT VECTORS.
ORTHO1(FRAME) ;ORTHOGONALIZE BY WORST CASE.
ORTHO2(FRAME) ;ORTHOGONALIZE BY K ← (I CROSS J), J ← (K CROSS I).
METRIC ROUTINES.
DETERM(FRAME)
ANGL3V(V1,V2,V3)
DISTANCE(ENTITY,ENTITY);
3.3 Image Synthesis Routines. {perspective projection}